<!-------- @HEADER
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 !  Zoltan Toolkit for Load-balancing, Partitioning, Ordering and Coloring
 !                  Copyright 2012 Sandia Corporation
 !
 ! Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
 ! the U.S. Government retains certain rights in this software.
 !
 ! Redistribution and use in source and binary forms, with or without
 ! modification, are permitted provided that the following conditions are
 ! met:
 !
 ! 1. Redistributions of source code must retain the above copyright
 ! notice, this list of conditions and the following disclaimer.
 !
 ! 2. Redistributions in binary form must reproduce the above copyright
 ! notice, this list of conditions and the following disclaimer in the
 ! documentation and/or other materials provided with the distribution.
 !
 ! 3. Neither the name of the Corporation nor the names of the
 ! contributors may be used to endorse or promote products derived from
 ! this software without specific prior written permission.
 !
 ! THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
 ! EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 ! IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 ! PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
 ! CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 ! EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 ! PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 ! PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 ! LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 ! NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 ! SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 !
 ! Questions? Contact Karen Devine	kddevin@sandia.gov
 !                    Erik Boman	egboman@sandia.gov
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 ! @HEADER
-------> 
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
   <meta name="GENERATOR" content="Mozilla/4.76 [en] (X11; U; Linux 2.4.2-2smp i686) [Netscape]">
  <meta name="sandia.approval_type" content="formal">
  <meta name="sandia.approved" content="SAND2007-4748W">
  <meta name="author" content="Zoltan PI">

   <title>Zoltan User's Guide:  Parallel Coloring</title>
</head>
<body bgcolor="#FFFFFF">

<div align=right><b><i><a href="ug.html">Zoltan User's Guide</a>&nbsp;
|&nbsp; <a href="ug_util.html">Next</a>&nbsp; |&nbsp; <a href="ug_color.html">Previous</a></i></b></div>

<h2>
<a NAME="Parallel Coloring"></a>Parallel Coloring</h2>
The parallel coloring algorithm in Zoltan is based on the work of
<a href="ug_refs.html#d1color">Boman et al.</a> for distance-1
coloring and <a href="ug_refs.html#d2color">Bozdag et al.</a> for
distance-2 coloring. It was implemented in Zoltan by Doruk Bozdag and
Umit V. Catalyurek, Department of Biomedical Informatics, the Ohio State
University.  Distance-1 coloring algorithm is an iterative data
parallel algorithm that proceeds in two-phased rounds. In the first
phase, processors concurrently color the vertices assigned to
them. Adjacent vertices colored in the same parallel step of this
phase may result in inconsistencies. In the second phase, processors
concurrently check the validity of the colors assigned to their
respective vertices and identify a set of vertices that needs to be
re-colored in the next round to resolve the detected
inconsistencies. The algorithm terminates when every vertex has been
colored correctly. To reduce communication frequency, the coloring
phase is further decomposed into computation and communication
sub-phases. In a communication sub-phase processors exchange recent
color information. During a computation sub-phase, a number of
vertices determined by the SUPERSTEP_SIZE parameter, rather than a
single vertex, is colored based on currently available color
information. With an appropriate choice of a value for SUPERSTEP_SIZE,
the number of ensuing conflicts can be kept low while at the same time
preventing the runtime from being dominated by the sending of a large
number of small messages.  The distance-2 graph coloring problem aims
at partitioning the vertex set of a graph into the fewest sets
consisting of vertices pairwise at distance greater than two from each
other. The algorithm is an extension of the parallel distance-1
coloring algorithm.

<br/><br/>

In distance-1 coloring, a
post-processing to coloring, named as <em>recoloring</em>, is also implemented
in Zoltan by Ahmet Erdem Sariyuce, Erik Saule and Umit V. Catalyurek,
Department of Biomedical Informatics, the Ohio State University. Its
details are presented in <a href="ug_refs.html#sariyuce">Sariyuce et
al.<a/>.  Recoloring is an iterative improvement algorithm first
proposed in <a href="ug_refs.html#culberson">Culberson 92<a/> for
sequential architecture. The algorithm uses an existing coloring of a
graph to produce an new coloring. The vertices of the graph are
sorted according to a given permutation of the colors so that vertices
with the same color are recolored concurrently. There are two modes
of the recoloring procedure that are controlled by 
RECOLORING_TYPE parameter. In asynchronous recoloring, the vertices
are colored using the same algorithm used for the original coloring;
the only difference is the ordering of the vertices, which is expected
to present less conflicts (and therefore is faster and leads to fewer
colors). In synchronous recoloring, each processor waits for its
neighboors to finish coloring the vertices of a given color before
starting to color the vertices of the next color. Using a simple first
fit color allocation policy, the algorithm guarantees that no
conflicts will be generated and that the number of colors will not
increase. The order in which the colors are considers is given by the
RECOLORING_PERMUTATION parameter. The forward order processes the
colors in increasing value of the color identifier; while the reverse
order processes them in the opposite order. The non-decreasing order
processes the colors so that the most used color in the graph is
colored last; while the non-increasing order is the opposite
order. The number of times the recoloring procedure is applied is
controlled by the RECOLORING_NUM_OF_ITERATIONS parameter (setting it
to zero disables recoloring).
 



<br>&nbsp;
<br>&nbsp;
<table WIDTH="100%" NOSAVE >

<!--
<tr>
<td VALIGN=TOP><b>Color_Method String:</b></td>

<td><b> </b></td>
</tr>
-->

<tr>
<td><b>Parameters:</b></td>

<td></td>
</tr>

<tr>
<td VALIGN=TOP>&nbsp;&nbsp; See <a href="ug_color.html">Coloring Algorithms</a>.</td>

<td></td>
</tr>

<tr>
<td VALIGN=TOP><b>Required Query Functions:</b></td>

<td></td>
</tr>

<tr>
<td></td>

<td><b><a href="ug_query_lb.html#ZOLTAN_NUM_OBJ_FN">ZOLTAN_NUM_OBJ_FN</a></b></td>
</tr>

<tr>
<td></td>

<td><b><a href="ug_query_lb.html#ZOLTAN_OBJ_LIST_FN">ZOLTAN_OBJ_LIST_FN</a></b>
</td>
</tr>

<tr VALIGN=TOP>

<td></td>
<td NOSAVE>
<b><a href="ug_query_lb.html#ZOLTAN_NUM_EDGES_MULTI_FN">ZOLTAN_NUM_EDGES_MULTI_F
N</a></b> or
<b><a href="ug_query_lb.html#ZOLTAN_NUM_EDGES_FN">ZOLTAN_NUM_EDGES_FN</a></b>
<br>
<b><a href="ug_query_lb.html#ZOLTAN_EDGE_LIST_MULTI_FN">ZOLTAN_EDGE_LIST_MULTI_F
N</a></b> or
<b><a href="ug_query_lb.html#ZOLTAN_EDGE_LIST_FN">ZOLTAN_EDGE_LIST_FN</a></b>
</td>

</tr>

</table>

<p>
<hr WIDTH="100%">[<a href="ug.html">Table of Contents</a>&nbsp; | <a href="ug_util.html">Next:&nbsp;
Data Services and Utilities</a> |&nbsp; <a href="ug_color.html">Previous:&nbsp; Coloring Algorithms</a>&nbsp; |&nbsp; <a href="https://www.sandia.gov/general/privacy-security/index.html">Privacy and Security</a>]
</body>
</html>
